package com.bo.day20240925;

import java.util.LinkedList;

/**
 * 判断是否为完全二叉树
 * 思路：
 * 1. 层序遍历，判断是否是完全二叉树
 * 违反完全二叉树条件：
 * 左子树有右子树，但是没有左子树
 * 遇到左右两个孩子不双全的节点,后面节点必须是叶子节点
 *
 * @Author: gpb
 * @Date: 2024/9/25 15:32
 * @Description:
 */
public class IsCBT {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node (int data) {
            this.value = data;
        }
    }

    public static boolean isCBT (Node head) {
        if (head == null) {
            return true;
        }
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(head);
        // 是否遇到过左右不双全的节点
        boolean leaf = false;
        // 记录左右节点
        Node left = null, right = null;
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            if (poll.left != null) {
                queue.add(poll.left);
                left = poll.left;
            }
            if (poll.right != null) {
                queue.add(poll.right);
                right = poll.right;
            }
            // 如果左孩子为空,右孩子不为空，说明不是完全二叉树
            // 在已遇到左右子节点不全的情况下，后面节点不能有子节点，遍历后面的节点都是叶子节点。
            if ((left == null && right != null)
                    || (leaf && (left != null || right != null))) {
                return false;
            }
            // 遇到左右孩子不全，记录
            if (left == null || right == null) {
                leaf = true;
            }
            // 清空记录
            left = right = null;
        }
        return true;
    }

    /**
     * 基于递归套路分析是否为完全二叉树
     * 需要满足四种条件：
     * 1. 左子树是满的，右子树是满的，左高=右高
     * 2. 左子树是满的，右子树是完全，左高=右高
     * 3. 左子树是满的，右子树是满的，左高=右高+1
     * 4. 左子树是完全，右子树是满的，左高=右高+1
     */

    // 定义Info信息体，存储是否是满二叉树、是否是完全二叉树、高度
    public static class Info {
        boolean isFull;
        boolean isCBT;
        int height;

        public Info (boolean isFull, boolean isCBT, int height) {
            this.isFull = isFull;
            this.isCBT = isCBT;
            this.height = height;
        }
    }

    public static boolean isCBT2 (Node head) {
        if (head == null) {
            return true;
        }
        return process(head).isCBT;
    }

    public static Info process (Node head) {
        if (head == null) {
            // 空树条件好定义，空树我们默认是满的，完全的二叉树，高度0
            return new Info(true, true, 0);
        }
        // 搜集左右子树信息
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        /**
         * 基于递归套路分析是否为完全二叉树
         * 需要满足四种条件：
         * 1. 左子树是满的，右子树是满的，左高=右高
         * 2. 左子树是满的，右子树是完全，左高=右高
         * 3. 左子树是满的，右子树是满的，左高=右高+1
         * 4. 左子树是完全，右子树是满的，左高=右高+1
         */
        // 高度：最大高度+1
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        // 左右子树都是满的，并且高度一样，则是满的
        boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
        // 四种条件
        // 1. 左右子树都是满的，并且高度一样，则是完全二叉树，可以复用 isFull
        boolean isCBT = isFull;
        // 2. 左子树是满的，右子树是完全，左高=右高，右子树是满二叉树
        if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
            isCBT = true;
        }
        // 3. 左子树是满的，右子树是满的，左高=右高+1，左子树是满二叉树
        else if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
            isCBT = true;
        }
        // 4. 左子树是完全，右子树是满的，左高=右高+1，左子树是满二叉树
        else if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
            isCBT = true;
        }
        return new Info(isFull, isCBT, height);
    }

//    public static boolean isCBT2(Node head) {
//        if (head == null) {
//            return true;
//        }
//        return process(head).isCBT;
//    }
//
//    // 对每一棵子树，是否是满二叉树、是否是完全二叉树、高度
//    public static class Info {
//        public boolean isFull;
//        public boolean isCBT;
//        public int height;
//
//        public Info(boolean full, boolean cbt, int h) {
//            isFull = full;
//            isCBT = cbt;
//            height = h;
//        }
//    }
//
//    public static Info process(Node X) {
//        if (X == null) {
//            return new Info(true, true, 0);
//        }
//        Info leftInfo = process(X.left);
//        Info rightInfo = process(X.right);
//
//
//
//        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
//
//
//        boolean isFull = leftInfo.isFull
//                &&
//                rightInfo.isFull
//                && leftInfo.height == rightInfo.height;
//
//
//        boolean isCBT = false;
//        if (isFull) {
//            isCBT = true;
//        } else { // 以x为头整棵树，不满
//            if (leftInfo.isCBT && rightInfo.isCBT) {
//
//
//                if (leftInfo.isCBT
//                        && rightInfo.isFull
//                        && leftInfo.height == rightInfo.height + 1) {
//                    isCBT = true;
//                }
//                if (leftInfo.isFull
//                        &&
//                        rightInfo.isFull
//                        && leftInfo.height == rightInfo.height + 1) {
//                    isCBT = true;
//                }
//                if (leftInfo.isFull
//                        && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
//                    isCBT = true;
//                }
//
//
//            }
//        }
//        return new Info(isFull, isCBT, height);
//    }

    // for test
    public static Node generateRandomBST (int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static Node generate (int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    public static void main (String[] args) {
        int maxLevel = 5;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            if (isCBT(head) != isCBT2(head)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }

}
